//
//  BinaryTree.m
//  AlgorithmDemo
//
//  Created by zxs on 2020/5/15.
//  Copyright © 2020 zxs. All rights reserved.
//

#import "BinaryTree.h"

@implementation BinaryTree
/**
 *  创建二叉排序树
 *  二叉排序树：左节点值全部小于根节点值，右节点值全部大于根节点值
 *
 *  @param values 数组
 *
  *  @return 二叉树根节点
 */
+ (BinaryTreeNode *)createTreeWithValues:(NSArray<NSNumber *> *)values {
    BinaryTreeNode *rootNode = nil;
    for (NSNumber *number in values) {
        NSInteger value = [number integerValue];
        rootNode = [BinaryTree addNode:rootNode value:value];
    }
    return rootNode;
}

/**
 *  向二叉排序树节点添加一个节点
 *
 *  @param rootNode 根节点
 *  @param value    值
 *
 *  @return 根节点
 */
+ (BinaryTreeNode *)addNode:(BinaryTreeNode *)rootNode value:(NSInteger)value {
    // 根节点不存在，创建节点
    if (rootNode == nil) {
        rootNode = [[BinaryTreeNode alloc] init];
        rootNode.value = value;
        NSLog(@"node:%@", @(value));
    } else if (value < rootNode.value) {
        NSLog(@"to left");
        // 值小于根节点，则插入到左子树；这是递归，左子树将做同样的事
        rootNode.leftChild = [BinaryTree addNode:rootNode.leftChild value:value];
    } else if (value > rootNode.value) {
        NSLog(@"to right");
        // 值大于根节点，则插入到右子树；这是递归，右子树将做同样的事
        rootNode.rightChild = [BinaryTree addNode:rootNode.rightChild value:value];
    } else {
        NSLog(@"二叉排序树没有键值相等的节点，值%@已存在，不能插入", @(value));
    }
    return rootNode;
}

/**
 *  先序遍历：先访问根，再遍历左子树，再遍历右子树。典型的递归思想。
 *
 *  @param rootNode 根节点
 *  @param handler  访问节点处理函数
 */
+ (void)preOrderTraverseTree:(BinaryTreeNode *)rootNode handler:(void(^)(BinaryTreeNode *treeNode))handler {
    if (rootNode) {
        // 先访问节点
        if (handler) {
            handler(rootNode);
        }
        // 再遍历左右子树
        [BinaryTree preOrderTraverseTree:rootNode.leftChild handler:handler];
        [BinaryTree preOrderTraverseTree:rootNode.rightChild handler:handler];
    }
}

/**
 *  中序遍历
 *  先遍历左子树，再访问根，再遍历右子树
 *
 *  @param rootNode 根节点
 *  @param handler  访问节点处理函数
 */
+ (void)inOrderTraverseTree:(BinaryTreeNode *)rootNode handler:(void(^)  (BinaryTreeNode *treeNode))handler {
    if (rootNode) {
        // 先遍历左子树
        [BinaryTree inOrderTraverseTree:rootNode.leftChild handler:handler];
        
        // 访问节点
        if (handler) {
            handler(rootNode);
        }
    
        // 最后遍历右子树
        [BinaryTree inOrderTraverseTree:rootNode.rightChild handler:handler];
    }
}

/**
 *  后序遍历
 *  先遍历左子树，再遍历右子树，再访问根
 *
 *  @param rootNode 根节点
 *  @param handler  访问节点处理函数
 */
+ (void)postOrderTraverseTree:(BinaryTreeNode *)rootNode handler:(void(^)(BinaryTreeNode *treeNode))handler {
    if (rootNode) {
        // 先遍历左右子树
        [BinaryTree postOrderTraverseTree:rootNode.leftChild handler:handler];
        [BinaryTree postOrderTraverseTree:rootNode.rightChild handler:handler];
        
        // 最后访问节点
        if (handler) {
            handler(rootNode);
        }
    }
}

/**
 * 翻转二叉树（又叫：二叉树的镜像）
 *
 * @param rootNode 根节点
 *
 * @return 翻转后的树根节点（其实就是原二叉树的根节点）
 */
+ (BinaryTreeNode *)invertBinaryTree:(BinaryTreeNode *)rootNode {
    // 空节点
    if (!rootNode) {
        return nil;
    }
    
    // 没有子节点
    if (!rootNode.leftChild && !rootNode.rightChild) {
        return rootNode;
    }
    
    // 左右子树递归
    [BinaryTree invertBinaryTree:rootNode.leftChild];
    [BinaryTree invertBinaryTree:rootNode.rightChild];
    
    // 左右节点交换
    BinaryTreeNode *tempNode = rootNode.leftChild;
    rootNode.leftChild = rootNode.rightChild;
    rootNode.rightChild = tempNode;
    return rootNode;
}

@end
